// 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

// 示例:

// 输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
// 输出:
// [
//   ["ate","eat","tea"],
//   ["nat","tan"],
//   ["bat"]
// ]
// 说明：

// 所有输入均为小写字母。
// 不考虑答案输出的顺序。

#include <vector>
#include <string>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <iostream>

using namespace std;

// 哈希，把每个单词排序
class Solution1 {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        vector<vector<string>> res{};
        int n = strs.size();
        for (int i{0}; i < n; ++i) {
            string str = strs[i];
            sort(str.begin(), str.end()); // 把每个单词排序
            if (m.find(str) == m.end()) { // 新出现的分组
                vector<string> temp{};
                m[str] = temp;
            }
            m[str].push_back(strs[i]);
        }
        for (auto it = m.begin(); it != m.end(); ++it) {
            res.push_back((*it).second);
        }
        return res;
    }
};

// 哈希，把每个单词的按字母个数重新建立新数组
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<vector<int>, vector<string>> m; 
        // unordered_map<vector<int>, vector<string>> m; // unordered_map不能使用vector<int>作为key
        int n = strs.size();
        for (int i{0}; i < n; ++i) {
            vector<int> vec(26, 0);
            func(strs[i], vec); // 把单词转换成字母出现个数表示的数组
            if (m.find(vec) == m.end()) {
                vector<string> temp{};
                m[vec] = temp;
            }
            m[vec].push_back(strs[i]);
        }
        vector<vector<string>> res{};
        for (auto it = m.begin(); it != m.end(); ++it) {
            res.push_back(it->second);
        }
        return res;
    }
    void func(const string& s, vector<int>& v) {
        for (int i{0}; i < s.size(); ++i) {
            ++v[s[i] - 'a'];
        }
    }
};

int main() {
    Solution s{};
    vector<string> strs{};
    strs.push_back("acb");
    strs.push_back("abc");
    strs.push_back("abcc");
    strs.push_back("osfo");
    strs.push_back("aaasfasf");
    strs.push_back("acoob");
    strs.push_back("aocbo");
    vector<vector<string>> res = s.groupAnagrams(strs);
    for (int i{0}; i < res.size(); ++i) {
        for (int j{0}; j < res[i].size(); ++j) {
            cout << res[i][j] << ' ';
        }
        cout << endl;
    }

    return 0;
}